Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Binary Tree Right Side View

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
Image
  • Expected Output: [1, 3, 7]
  • Justification:
    • The last node at level 0 is 1.
    • The last node at level 1 is 3.
    • The last node at level 2 is 7.

Example 2

  • Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]
Image
  • Expected Output: [12, 1, 5, 3]
  • Justification:
    • The last node at level 0 is 12.
    • The last node at level 1 is 1.
    • The last node at level 2 is 5.
    • The last node at level 3 is 3.

Example 3

  • Input: root = [8, 4, 9, 3, null, null, 10, 2]
Image
  • Expected Output: [8, 9, 10, 2]
  • Justification:
    • The last node at level 0 is 8.
    • The last node at level 1 is 9.
    • The last node at level 2 is 10.
    • The last node at level 3 is 2.

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Solution

To solve this problem, we will use the Breadth-First Search (BFS) agorithm to traverse the binary tree and compute the right view of the tree. It processes the tree level by level, ensuring that at each level, the last node encountered (rightmost node) is stored in the result list. A queue is used to facilitate level-wise traversal, and at the end of each level, the last node is added to the result.

Step-by-Step Algorithm

  1. Base Case: If the root is null, return an empty list since there are no nodes to process.

  2. Initialize Queue: Create an empty queue and add the root node to it. This queue is used to traverse the tree level by level, starting from the root.

  3. While the Queue is Not Empty:

    • Determine Level Size: Calculate the number of nodes at the current level using queue.size(). This ensures that we process all nodes at the same level before moving to the next level.

    • Process Each Node at the Current Level:

      • For each node in the current level:
        • Dequeue the Current Node: Poll the node from the front of the queue.
        • Add its Left Child to the Queue: If the current node has a left child, add it to the queue to process in the next level.
        • Add its Right Child to the Queue: If the current node has a right child, add it to the queue for the next level.
    • Add the Last Node of the Level to the Result: After processing all nodes at the current level, add the value of the last node (rightmost node) to the result list. This node will represent the right view at that level.

  4. Repeat: Continue this process for each level until the queue is empty, meaning all levels have been processed.

  5. Return the Result: After processing all levels, the result list will contain the nodes visible from the right view of the tree.

Algorithm Walkthrough

Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]

Image

Step-by-Step Execution

  1. Initialization:

    • The root node is 12. Add 12 to the queue.

    Queue: [12] Result: []

  2. Level 1:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 12.
    • Add its left child (7) and right child (1) to the queue.
    • Add 12 in the result list.

    Queue: [7, 1] Result: [12]

  3. Level 2:

    • queue.size() is 2, meaning there are 2 nodes at this level.
    • Dequeue node 7. Add its right child (9) to the queue (it has no left child).
    • Dequeue node 1. Add its left child (10) and right child (5) to the queue.
    • Since 1 is the last node at this level, add it to the result.

    Queue: [9, 10, 5] Result: [12, 1]

  4. Level 3:

    • queue.size() is 3, meaning there are 3 nodes at this level.
    • Dequeue node 9. Add its right child (3) to the queue (it has no left child).
    • Dequeue node 10. It has no children.
    • Dequeue node 5. It has no children.
    • Since 5 is the last node at this level, add it to the result.

    Queue: [3] Result: [12, 1, 5]

  5. Level 4:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 3. Since it's the only node at this level, add it to the result.
    • Node 3 has no children, so nothing is added to the queue.

    Queue: [] Result: [12, 1, 5, 3]

  6. Completion: The queue is now empty, meaning all levels of the tree have been processed. The right view of the tree is complete.

Final Output: [12, 1, 5, 3]

Code

Here is the code for this algorithm:

Java

. . . .

Time Complexity

The time complexity of the above algorithm is , where ā€˜N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

  • The space complexity of the above algorithm will be for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.
  • Also, we use space space for result list. For the skewed tree we need to store all N elements in the result list.

Similar Questions

Problem 1: Given a binary tree, return an array containing nodes in its left view. The left view of a binary tree is the set of nodes visible when the tree is seen from the left side.

Solution: We will be following a similar approach, but instead of appending the last element of each level, we will be appending the first element of each level to the output array.

Binary Tree Right Side View (medium)
Sort Colors (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Time Complexity

Space Complexity

Similar Questions